Local Area Networks (LANs) connect computing systems together. LANs of all types can be connected together using Media Access Control (MAC) bridges, as set forth in the “IEEE Standard for Information Technology, Telecommunications and Information Exchange between Systems, Local and Metropolitan Area Networks, Common Specifications, Part 3: Media Access Control (MAC) Bridges,” published as ANSI/IEEE Standard 802.1D (1998), which is incorporated herein by reference. The 802.1D standard is available at standards.ieee.org/catalog/IEEE802.1.html.
Each computing system connects to a LAN through a MAC device. MAC bridges that implement the 802.1D standard allow MAC devices attached to separate LANs to appear to each other as if they were attached to a single LAN. A MAC bridge functions within the Logical Link Control (LLC) sublayer of the Network Layer defined in ISO/IEC standard 7498-1: 1994, entitled “Information Processing Systems—Open Systems Interconnection-Basic Reference Model—Part 1: The Basic Model” (available from the American National Standards Institute, New York, N.Y.), which is incorporated herein by reference. The bridge includes two or more MAC devices that interconnect the bridge ports to respective LANs.
MAC bridges utilize a database to map destination MAC addresses located in the packets to bridge ports. The bridge builds the database by means of a learning process, in which it associates the source MAC address of each incoming packet with the port on which the packet was received. When the bridge receives an incoming packet whose destination address is not located in the database, it broadcasts the packet on all its available ports, except the one the packet arrived on. MAC bridges that do not recognize the destination address will further broadcast the packet. Through the broadcast mechanism, the packet will eventually traverse all interconnected bridges at least once.
Loops in the network topology can cause these broadcast packets to flood the network. If the packet's destination address is not recognized at any point in the loop, the packet may continue to traverse the loop forever. The topology of bridge interconnections must be managed to prevent packets traveling in loops between bridges that propagate the broadcast packet. For this purpose, the IEEE 802.1D standard specifies an implementation of a spanning tree protocol (STP) and algorithm, for managing the creation and updating of the network topology. STP ensures that all data paths in a network of bridges are free of loops by disabling forwarding of packets through certain interfaces. The spanning tree algorithm and protocol thus configure a simply-connected active topology from the arbitrarily-connected components of the network. The spanning tree algorithm takes advantage of a standard feature of MAC ports: the ports may be either in a blocking state or a forwarding state. Frames are forwarded through ports in a MAC bridge in the forwarding state, and not through ports in the blocking state. At any time, bridges effectively connect just the LANs to which ports in a forwarding state are attached. Ports that are in a blocking state do not forward frames.
The spanning tree algorithm defines one bridge in the network as the root bridge. Each LAN connected to the network has a bridge port that connects it to the root bridge. This port is known as the designated port for the LAN, and the bridge of which the designated port is part is known as the designated bridge for the LAN. The root bridge is the designated bridge for each LAN to which it is connected. Each bridge has a port defined as the root port, which uniquely connects the bridge to the root bridge. All ports on the bridge that are neither the root port nor the designated port are put into the blocking state.
In determining which port should be used as the root port, STP defines a path cost associated with each path out of the ports in a bridge. The sum of the active path costs from a designated bridge port to the root bridge is defined as the root path cost. STP also defines a priority for each port on each bridge. In its simplest form, the port priority is the numerical value of the port identifier. If there is more than one possible path from a designated bridge port to the root bridge, STP specifies that the path with the lowest cost will be chosen. Frames destined to cross the network will travel from the originating LAN's designated bridge along a root path toward the root bridge. If the destination bridge does not lie along the root path, the frame will be routed through the root bridge and travel along a root path from the root bridge to the designated port for the destination LAN.
STP defines a method of communicating the information necessary for computing root paths in a network. MAC bridges that conform to the IEEE 802.1D standard transmit control information using bridge protocol data units (BPDUs). A MAC frame conveying a BPDU is received by all the bridges connected to the LAN on which the frame is transmitted. BPDUs are not directly forwarded by bridges, but the information in them may be used by a bridge in calculating its own BPDU to transmit, and may stimulate that transmission. STP uses configuration BPDUs to determine the network topology, as is laid out in the IEEE 802.1D standard (section 8.3.2):                “Each configuration BPDU contains, among other parameters, the unique identifier of the bridge that the transmitting bridge believes to be the root, the cost of the path to the root from the transmitting port, the identifier of the transmitting bridge, and the identifier of the transmitting port. This information is sufficient to allow a receiving bridge to determine whether the transmitting port has a better claim to be the designated port on the LAN on which the configuration BPDU was received than the port currently believed to be the designated port, and to determine whether the receiving port should become the root port for the bridge if it is not already.        “Timely propagation throughout the bridged LAN of the necessary information to allow all bridge ports to determine their state (blocking or forwarding) is achieved through three basic mechanisms:        “a) A bridge that believes itself to be the root (all bridges start by believing themselves to be the root until they discover otherwise) originates configuration messages (by transmitting configuration BPDUs) on all the LANs to which it is attached, at regular intervals.        “b) A bridge that receives a configuration BPDU on what it decides is its root port conveying better information (i.e., highest priority root identifier, lowest root path cost, highest priority transmitting bridge and port), passes that information on to all the LANs for which it believes itself to be the designated bridge.        “c) A bridge that receives inferior information, on a port it considers to be the designated port on the LAN to which it is attached, transmits its own information in reply, for all other bridges attached to that LAN to hear.        “Hence, spanning tree paths to the bridge with highest priority root identifier are quickly learned throughout the bridged LAN, with inferior information about other potential roots and paths being contradicted.”        
STP is guaranteed to converge within a finite period of time to a network topology with no loops, given an arbitrary initial topology. Note that the description of STP in the IEEE 802.1D standard does not specify a method for calculating the cost of the path to the root from the transmitting port. While STP is guaranteed to converge, the path costs will determine the optimality of the solution obtained.
Multiprotocol Label Switching (MPLS) is gaining popularity as a method for efficient transportation of data packets over connectionless networks, such as Internet Protocol (IP) networks. MPLS is described in detail by Rosen et al., in Request for Comments (RFC) 3031 of the Internet Engineering Task Force (IETF), entitled “Multiprotocol Label Switching Architecture” (January, 2001), which is incorporated herein by reference. This RFC is available at www.ietf.org/rfc.html. In conventional connectionless packet routing, each router along the path of a packet sent through the network analyzes the packet header and independently chooses the next hop for the packet by running a routing algorithm. In MPLS, however, each packet is assigned to a Forwarding Equivalence Class (FEC) when it enters the network, depending on its destination address. A short, fixed-length label identifying the FEC to which the packet belongs is pushed onto the top of a label stack, which is attached to the packet at the FEC ingress point. All packets in a given FEC are passed through the network over the same path by label-switching routers (LSRs). Unlike IP routers, LSRs simply use the packet label as an index to a look-up table, which specifies the next hop on the path for each FEC and the label that the LSR should attach to the packet for the next hop. The LSR pops the top label off the label stack, examines its destination address, and pushes another label onto the stack with the destination of the next hop.
The flow of packets along a label-switched path (LSP) under MPLS is completely specified by the label applied at the ingress of the path. A LSP is essentially a tunnel through the network, useful in network traffic management and communication security. MPLS tunnels are established by “binding” a particular label, assigned at the ingress node to the network, to a particular FEC.
Lasserre et al. describe a method to create a virtual LAN using a MPLS network in “Transparent VLAN services over MPLS” (July 2001), which is incorporated herein by reference. This document is available at search.ietf.org/internet-drafts/draft-lasserre-tls-mpls-0.txt. A transparent LAN service (TLS) provides bridge-like functionality between multiple sites over a large network. Users connect to the TLS via regular node interfaces, and LSPs between the nodes to which the users are connected form the TLS entity itself. Every node in a TLS acts as a virtual bridge. A virtual bridge node has “virtual ports,” which are the endpoints of LSPs that are part of the TLS. The interfaces to which the users are actually connected are “real” ports. Both virtual and real interfaces are treated identically from the point of view of bridge processing (frame forwarding policies and loop prevention). A single LSP can participate in multiple TLS instances, each belonging to a different user.
The TLS network topology is completely specified by the LSP connections, which in turn depend on the MPLS protocol to actually transfer the packets through the virtual tunnels. Since MPLS networks supply an alternative, virtual implementation of layer 2 network communications, TLS can be thought of as parallel to conventional virtual bridged local area networks, as specified in the IEEE 802.1Q standard. From the perspective of the end user, a TLS network is transparent. The user is provided with the illusion that the LSPs are single-hop connections between adjacent routers.
TLS networks are still in the development stage, and there are as yet no clear standards for loop prevention in such networks. One possible solution to removing loops in TLS topologies is to configure the TLS network as a full mesh of tunnels, as suggested by Lasserre et al. in the above-mentioned draft, but the full-mesh topology is costly and difficult to maintain. Therefore, a preferred solution is to run STP on the TLS network, as described, for example, by Senevirathne in “Use of Partial Meshed Tunnels to Achieve Forwarding Behavior of Full Meshed Tunnels” (June 2001), which is incorporated herein by reference. This document is available at search.ietf. org/internet-drafts/draft-tsenevir-12vpn-pmesh-00.txt. Senevirathne describes a method of separating STP into user and provider spaces. STP information is carried across the provider space in the network using extensions to the Border Gateway Protocol (BGP) and the Open Shortest Path First (OSPF) protocol.
Network ring topologies are well known in the art of synchronous networks (such as SONET) and are being increasingly used in Internet Protocol (IP) networks, as well. Ring networks enable carriers to offer large bandwidth to users in a cost-effective manner. They also lend themselves to fast rerouting in the event of network failures, since two alternative routes—in clockwise and counterclockwise directions—are generally available for connecting any two nodes on the ring. Some recently-developed bidirectional protocols provide efficient bandwidth utilization by enabling data to be transferred between any pair of nodes in either direction around the ring, while maintaining fast protection against faults.
The leading bidirectional protocol for high-speed packet rings is the Resilient Packet Rings (RPR) protocol, which is in the process of being defined as IEEE standard 802.17. Network-layer routing over RPR is described, for example, by Jogalekar et al., in “IP over Resilient Packet Rings” (Internet Draft draft-jogalekar-iporpr-00), and by Herrera et al., in “A Framework for IP over Packet Transport Rings” (Internet Draft draft-ietf-ipoptr-framework-00). A proposed solution for Media Access Control (MAC—protocol layer 2) in bidirectional ring networks is the Spatial Reuse Protocol (SRP), which is described by Tsiang et al., in Request for Comments (RFC) 2892 of the Internet Engineering Task Force (IETF). All these documents are incorporated herein by reference. They are available at www.ietf.org.